#include<iostream>
#include<list>
#include<queue>
#include<stack>
using namespace std;

struct TreeNode
{
    char value;
    list<TreeNode*> listChildren;
    
    TreeNode(void)
    : value(0)
    {
    }
};

class Tree
{
public:
    Tree(void)
    :root(NULL)
    {
    }
    ~Tree(void)
    {
        FreeNode(root);
    }
    void BuildTreeFrom(char const* expression)
    {
        stack<TreeNode*> stkNode;
        char const* pExpr = expression;
        
        while ('\0' != *pExpr)
        {
            switch (*pExpr)
            {
            case '(':
                break;
            case ',':
            case ')':
                stkNode.pop();
                break;
            default:
                TreeNode* pNewNode = new TreeNode;
                pNewNode->value = *pExpr;
                
                if (NULL == root)
                {
                    root = pNewNode;
                }
                else
                {
                    TreeNode* pNode = stkNode.top();
                    pNode->listChildren.push_back(pNewNode);
                }
                
                stkNode.push(pNewNode);
                break;
            }
            
            pExpr++;
        }
    }
    void Output(void)
    {
        stack<TreeNode*> stkNode;
        stack<int> stkIndex;
        TreeNode* pNode = root;
        
        char strTemp[100] = {0};
        char* pStr = strTemp;
        *pStr++ = '(';
        
        while (NULL != pNode || !stkNode.empty())
        {
            if (NULL != pNode)
            {
                *pStr++ = pNode->value;
                *pStr++ = '(';
                
                stkNode.push(pNode);
                stkIndex.push(0);
                
                if (!pNode->listChildren.empty())
                {
                    pNode = pNode->listChildren.front();
                }
                else
                {
                    pNode = NULL;
                }
            }
            else
            {
                stkNode.pop();
                if (stkNode.empty())
                {
                    pStr--;
                    *pStr++ = ')';
                    *pStr = ')';
                    
                    break;
                }
                
                pNode = stkNode.top();
                stkIndex.pop();
                stkIndex.top()++;
                
                pStr--;
                if (',' == *pStr)
                {
                    *pStr++ = ')';
                }
                *pStr++ = ',';
                
                list<TreeNode*>::iterator it = pNode->listChildren.begin();
                advance(it, stkIndex.top());
                if (it != pNode->listChildren.end())
                {
                    pNode = *it;
                }
                else
                {
                    pNode = NULL;
                }
            }
        }
        
        cout<< strTemp <<endl;
    }
    void PreorderTraverse(void)
    {
        PreorderTraverse(root);
    }
    void PostorderTraverse(void)
    {
        PostorderTraverse(root);
    }
    void HierarchyTraverse(void)
    {
        queue<TreeNode*> queNode;
        queNode.push(root);

        while (!queNode.empty())
        {
            TreeNode* pNode = queNode.front();
            cout<< pNode->value << " ";
            
            list<TreeNode*>::iterator it, itEnd = pNode->listChildren.end();
            for (it = pNode->listChildren.begin(); it != itEnd; ++it)
            {
                queNode.push(*it);
            }
            queNode.pop();
        }
    }
    
private:
    TreeNode* root;
    void FreeNode(TreeNode* pNode)
    {
        if (NULL != pNode)
        {
            list<TreeNode*>::iterator it, itEnd = pNode->listChildren.end();
            for (it = pNode->listChildren.begin(); it != itEnd; ++it)
            {
                FreeNode(*it);
            }
            
            delete pNode;
            pNode = NULL;
        }
    }
    void PreorderTraverse(TreeNode* pNode)
    {
        if (NULL == pNode)
        {
            return;
        }
        
        cout<< pNode->value << " ";
        list<TreeNode*>::iterator it, itEnd = pNode->listChildren.end();
        for (it = pNode->listChildren.begin(); it != itEnd; ++it)
        {
            PreorderTraverse(*it);
        }
    }
    void PostorderTraverse(TreeNode* pNode)
    {
        if (NULL == pNode)
        {
            return;
        }
        
        list<TreeNode*>::iterator it, itEnd = pNode->listChildren.end();
        for (it = pNode->listChildren.begin(); it != itEnd; ++it)
        {
            PostorderTraverse(*it);
        }
        cout<< pNode->value << " ";
    }
};

int main(void)
{
    Tree testTree;
    testTree.BuildTreeFrom("(A(B(E,F),C,D(G(H(I,J,K)))))");
    
    testTree.PreorderTraverse();
    cout<< "\n";
    testTree.PostorderTraverse();
    cout<< "\n";
    testTree.HierarchyTraverse();
    cout<< "\n";
    
    testTree.Output();
    
    system("pause");
}
